//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2002-2004
//
// Generalization algorithms.
//

# include "StdAfx.h"
# include "Generalize.h"
# include "PtAlgo.h"

static
size_t _Generalize (points_t & _points, size_t _a, size_t _b, float _d2, float _fCosY) {
	if (_a + 1 >= _b)
		return 0;

	assert (_b < _points.size ());
	const point_t & pa = _points [_a];
	const point_t & pb = _points [_b];
	const float dx = (pb.x - pa.x)*_fCosY;
	const float dy = pb.y - pa.y;
	const float r2 = dx*dx + dy*dy;

	// Find the most distant point relative to AB.
	size_t c_max = _a;
	float d2_max = 0;
	for (size_t c = _a + 1; c < _b; ++ c) {
		const point_t & pc = _points [c];

		const float t  = r2 > 0 ? (pc.y - pa.y)*dx - (pc.x - pa.x)*dy*_fCosY : 0;
		// Distance^2 from C to AB.
		const float d2 = r2 > 0 ? t*t/r2 : (pc.x - pa.x)*(pc.x - pa.x)*_fCosY*_fCosY + (pc.y - pa.y)*(pc.y - pa.y);
		if (d2 > d2_max) {
			d2_max = d2;
			c_max = c;
		}
	}

	if (d2_max < _d2) {
		// Remove all points between (A,B).
		_points.erase (_points.begin () + _a + 1, _points.begin () + _b);

		return _b - (_a + 1);
	} else {
		// Apply recursively to (Cmax,B).
		const size_t cDeleted1 = _Generalize (_points, c_max, _b, _d2, _fCosY);
		// Apply recursively to (A,Cmax).
		const size_t cDeleted2 = _Generalize (_points, _a, c_max, _d2, _fCosY);

		return cDeleted1 + cDeleted2;
	}
}

size_t Generalize (points_t & _points, float _d, float _fCosY) {
	//
	// The Douglas-Peuker algorithm.
	//

	const size_t cPoints = _points.size ();
	if (cPoints <= 2)
		return 0;

	return _Generalize (_points, 0, cPoints - 1, _d*_d, _fCosY);
}

size_t GeneralizePart (points_t & _points, size_t _a, size_t _b, float _d, float _fCosY) {
	if (_a > _b || _b - _a + 1 <= 2)
		return 0;

	return _Generalize (_points, _a, _b, _d*_d, _fCosY);
}